package class04

import (
	"sort"
)

/*
	每个信封都有长款两个维度，A信封如果想套在B信封里面，A信封必须在
	长和款上都要小于B信封才行。
	如果给你一批信封，返回最大嵌套层数
	思路：
		将信封宽度从小到大排序，宽度相等时，按长度从大到小排列
		然后对长度求最长递增子序列，最大长度即为最大嵌套层数。
	matrix: [
		[2, 5], // 长
		[3, 7],	// 宽
	]
*/
func maxEnvelopes(matrix [][]int) int {
	sortedEnvelopes := GetSortedEnvelope(matrix)
	sortHeights := make([]int, len(sortedEnvelopes))
	for i:=0; i<len(sortedEnvelopes); i++ {
		sortHeights[i] = sortedEnvelopes[i].height
	}
	dp := make([]int, len(sortHeights))
	ends := make([]int, len(sortHeights))
	dp[0] = 1
	ends[0] = sortHeights[0]
	right := 0 // ends 的有效区间
	var l, r, mid int
	for i:=0; i<len(sortHeights); i++ {
		l = 0
		r = right
		mid = (l+r)/2
		for l <= r {
			if sortHeights[i] > ends[mid] {
				l = mid + 1
			} else {
				r = mid - 1
			}
		}
		right = max(right, l)
		ends[l] = sortHeights[i]
		dp[i] = l + 1
	}
	return right + 1
}

func GetSortedEnvelope(matrix [][]int) Envelopes {
	enves := make([]Envelope, len(matrix[0]))
	for i:=0; i<len(matrix[0]); i++ {
		enves[i] = Envelope{
			width: matrix[0][i],
			height: matrix[1][i],
		}
	}
	sort.Sort(Envelopes(enves))
	return enves
}

type Envelopes []Envelope

func (e Envelopes) Len() int {
	return len(e)
}

func (e Envelopes) Less(i, j int) bool {
	if e[i].width < e[j].width {
		return true
	} else if e[i].width == e[j].width {
		return e[i].height > e[j].height
	} else {
		return false
	}
}

func  (e Envelopes) Swap (i, j int) {
	e[i], e[j] = e[j], e[i]
}


type Envelope struct {
	width  int
	height int
}
